package bin_tree;

/**
 * @author yuisama
 * @date 2023/03/23 21:13
 * 基础二叉树的实现
 **/
public class MyBinTree {
    private class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;
        public TreeNode(char val) {
            this.val = val;
        }
    }

    public TreeNode build() {
        TreeNode node1 = new TreeNode('A');
        TreeNode node2 = new TreeNode('B');
        TreeNode node3 = new TreeNode('C');
        TreeNode node4 = new TreeNode('D');
        TreeNode node5 = new TreeNode('E');
        TreeNode node6 = new TreeNode('F');
        TreeNode node7 = new TreeNode('G');
        TreeNode node8 = new TreeNode('H');
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node5.right = node8;
        node3.left = node6;
        node3.right = node7;
        return node1;
    }
    // 传入一颗以root为根的二叉树，就能按照前中后序的方式遍历这棵二叉树
    // 现在的遍历就是输出节点的值
    public void preOrder(TreeNode root) {
        // 1.base case
        if (root == null) {
            return;
        }
        // 根
        System.out.print(root.val + " ");
        // 左
        preOrder(root.left);
        preOrder(root.right);
    }
    // 传入一颗以root为根的二叉树，就能按照左右根的方式进行遍历
    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        // 先左子树的中序
        inOrder(root.left);
        // 根
        System.out.print(root.val + " ");
        // 再右子树的中序
        inOrder(root.right);
    }

    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        // 先左子树的后序
        postOrder(root.left);
        // 再右子树的后序
        postOrder(root.right);
        // 根
        System.out.print(root.val + " ");
    }
    // 在当前以root为根的二叉树中，判断值为val的元素是否存在
    public boolean contains(TreeNode root,char val) {
        // 1.base case
        if (root == null) {
            return false;
        }
        if (root.val == val) {
            return true;
        }
        return contains(root.left,val) || contains(root.right,val);
    }

    /**
     * 传入一颗以root为根的二叉树，就能求出该树的结点个数
     * @param root
     * @return
     */
    public int treeNodeSize(TreeNode root) {
//        // 1.base case
//        if (root == null) {
//            return 0;
//        }
//        // 整棵树的结点个数 = 自己1 + 左子树的所有节点 + 右子树的所有节点
//        return 1 + treeNodeSize(root.left) + treeNodeSize(root.right);
        return root == null ? 0 : 1 + treeNodeSize(root.left) + treeNodeSize(root.right);
    }
    // 传入一颗以root为根的二叉树，就能求出第k层的结点个数
    public int getKLevelNodes(TreeNode root,int k) {
        // 1.base case
        if (root == null || k <= 0) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        // 第k层的结点个数 = 左子树的第k-1层结点个数 +右子树的第k - 1层结点个数
        return getKLevelNodes(root.left,k - 1)
                + getKLevelNodes(root.right,k - 1);
    }

    /**
     * 传入一颗以root为根的二叉树，就能统计出当前这棵树的叶子结点的个数
     * @param root
     * @return
     */
    public int leafNodes(TreeNode root) {
        // 1.base case
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        // 总的叶子结点个数 = 左子树的叶子节点个数 + 右子树的叶子结点个数
        return leafNodes(root.left) + leafNodes(root.right);
    }

    /**
     * 传入一颗以root为根的二叉树，就能求出该树的高度
     * @param root
     * @return
     */
    public int height(TreeNode root) {
        // 1.base case
//        if (root == null) {
//            return 0;
//        }
//        // 总高度 = 1 + Math.max(左子树高度，右子树高度)
//        return 1 + Math.max(height(root.left),height(root.right));
        return root == null ? 0 : 1 + Math.max(height(root.left),height(root.right));
    }

    public static void main(String[] args) {
        MyBinTree tree = new MyBinTree();
        TreeNode root = tree.build();
        // 4
        System.out.println(tree.getKLevelNodes(root,3));
    }

}